|
In a cellular automaton, a Garden of Eden configuration is a configuration that cannot appear on the lattice after one time step, no matter what the initial configuration. In other words, these are the configurations with no predecessors. They resemble the concept of the Garden of Eden in Abrahamic religions, which was created out of nowhere, hence the name. According to , this name was coined by John Tukey in the 1950s. A Garden of Eden is a configuration of the whole lattice (usually a one- or two-dimensional infinite square lattice). Each Garden of Eden configuration contains at least one finite pattern (an assignment of states to a finite subset of the cells) that has no predecessor regardless of how the surrounding cells are filled. Such a pattern is called an orphan. Alternatively, an orphan is a finite pattern such that each configuration containing that pattern is a Garden of Eden. == Searching for the Garden of Eden == For one-dimensional cellular automata, Gardens of Eden can be found by an efficient algorithm (running in time polynomial in the size of the rule table of the automaton). For higher dimensions, determining whether a Garden of Eden exists is an undecidable problem, meaning that there is no algorithm that can be guaranteed to terminate and produce the correct answer.〔 Nevertheless, in many cases it is possible to use the Garden of Eden theorem (below) to infer that a solution exists and then use a search algorithm to find one. It would be possible for a computer program to search for orphan patterns by systematically examining all possible patterns, in order by increasing size, and by testing all possible predecessors for each pattern to determine whether it is in fact an orphan. However, the number of patterns that would need to be generated to find a Garden of Eden in this way is exponential in the area of the pattern. This enormous number of patterns would make this type of brute-force search prohibitively expensive, even for relatively small sizes of patterns. pioneered a more efficient computational approach for finding orphan patterns. His method is based on the theory of formal languages, and takes an amount of time that is exponential in the width of the pattern rather than its area. The key idea is that, for any fixed width, it is relatively straightforward to construct a nondeterministic finite automaton that recognizes patterns of a given width that have a predecessor. The input symbols to this machine describe each row of the pattern, and the states of the machine describe the nearby rows of possible predecessors for the part of the pattern that has been input so far. One can construct from this machine another finite state machine that recognizes the complementary set, the patterns that do not have predecessors, by converting the nondeterministic finite state machine to a deterministic finite automaton and then complementing its set of accepting states. Once a machine recognizing the complementary set has been constructed, one may test whether the language it recognizes is empty, by searching for a path from the start state to an accepting state. This path, if it exists, gives a row-by-row description of an orphan pattern. The first known Garden of Eden pattern in Conway's Game of Life, fitting in a rectangle, was identified as a candidate to be a Garden of Eden by Roger Banks in 1971, and then verified by an exhaustive backtracking search for predecessors.〔In ''Lifeline'' (Vol. 3 ) (September 1971), editor Robert T. Wainwright announced that Roger Banks and Steve Ward had proven the existence of a Garden of Eden within a rectangle, and presented a pattern believed by Banks to be a Garden of Eden. In ''Lifeline'' (Vol. 4 ) (December 1971), Wainwright reported that a group at Honeywell using software by Don Woods had verified Banks' pattern to be a Garden of Eden. See also .〕 Subsequently, Hardouin-Duparc used his formal language approach to find the narrowest possible Gardens of Eden in Conway's Game of Life, only six cells wide. The smallest known orphan pattern in Conway's Game of Life was found by Marijn Heule, Christiaan Hartman, Kees Kwekkeboom and Alain Noels in December 2011. It has 56 living cells and fits in an 10x10 square. To find this pattern, they made an assumption that the pattern to be found was symmetric (greatly reducing the search space) and used a Boolean satisfiability problem solver to test whether each candidate pattern was an orphan. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Garden of Eden (cellular automaton)」の詳細全文を読む スポンサード リンク
|